package Leetcode第二期;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @author : K k
 * @date : 11:06 2020/9/21
 */
public class 最小栈_155 {
    //最优解：双队列 一个双向队列，一个放最小值队列

    //不是最优解 思路：单队列+最小值
    private Queue<Integer> queue;
    private int min=Integer.MAX_VALUE;

    /** initialize your data structure here. */
    public 最小栈_155() {
        queue=new LinkedList<>();
    }

    public void push(int x) {
        queue.offer(x);
        for (int i = queue.size() - 1; i > 0; i--) {
            queue.offer(queue.poll());
        }
        min=Math.min(x,min);
    }

    public void pop() {
        Integer poll = queue.poll();
        if(min==poll){
            //重新找最小值
            Queue<Integer> tmp=new LinkedList<>();
            min=Integer.MAX_VALUE;
            while (!queue.isEmpty()){
                //遍历
                Integer next = queue.poll();
                min=Math.min(min,next);
                tmp.offer(next);
            }
            queue=tmp;
        }
    }

    public int top() {
        return queue.peek();
    }

    public int getMin() {
        return min;
    }
}
